/*
 *Copyright (c) [2019] [name of copyright holder]
 *[Software Name] is licensed under the Mulan PSL v1.
 *You can use this software according to the terms and conditions of the Mulan PSL v1.
 *You may obtain a copy of Mulan PSL v1 at:
 *http://license.coscl.org.cn/MulanPSL
 *THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND, EITHER EXPRESS OR
 *IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT, MERCHANTABILITY OR FIT FOR A PARTICULAR
 *PURPOSE.
 *See the Mulan PSL v1 for more details.
 */

/*!
 * \autor captainpeng
 * \date 2019-12-13
 * \update 2019-12-13
 * \version 1.0
 * \copyright
 */

#ifndef MY_MEMSPLAYTREE_HPP
#define MY_MEMSPLAYTREE_HPP
#include<cassert>
#include<cstdint>

#include"memFunc.hpp"

#define CHECKNOW(now) assert((now) < MAX_DEPTH)
#define ALLOCERR() assert(false)
namespace my{

    class memSplayNode{
    public:
        using valueType = void *;
        using sizeType = int;
        using countType = unsigned short;
        using markType = unsigned short;
        void * mValue; // 分配内存的地址
        int mSize; // 分配内存地址的大小
        unsigned short mCount; // 计数器
        unsigned short mMark; // 标记
        memFreeFunc mFree; //进行 delete 的函数指针

        memSplayNode * mLeft; // 左子树
        memSplayNode * mRight; // 右子树

        memSplayNode():
            mValue(nullptr),
            mSize(0),
            mCount(0),
            mMark(0),
            mFree(nullptr),
            mLeft(nullptr),
            mRight(nullptr)
        {}

        memSplayNode(void * val, int size, unsigned short count, unsigned char mark, memFreeFunc free):
            mValue(val),
            mSize(size),
            mCount(count),
            mMark(mark),
            mFree(free),
            mLeft(nullptr),
            mRight(nullptr)
        {}

        ~memSplayNode(){
            // std::cout<<"~SplayNode "<<mValue<<", mRight "<<(void *)mRight<<", mLeft "<<(void *)mLeft<<std::endl;
            (*mFree)(mValue);
            delete mRight;
            delete mLeft;
        }

        bool isAt(void * val){
            void * value = static_cast<void *>(static_cast<uint8_t *>(mValue) + mSize);
            // std::cout<<"isAt "<<(val >= mValue && val < value)<<" "<<(void *)value<<" mSize == "<<mSize<<std::endl;
            return val >= mValue && val < value;
        }

        inline void plusCount(){
            ++mCount;
        }
        
        inline void minusCount(){
            if(mCount > 0) --mCount;
        }
    };

    class memSplayTree{
    public:
        using nodeType = memSplayNode;
        using treeType = memSplayNode *;

        static const int MAX_DEPTH = 1024;
        static const int MAX_MARK = UINT16_MAX;
        static const int MAX_MARK_SIZE  = (UINT16_MAX+1)/64;
        
    private:
        
        static treeType Depth[MAX_DEPTH];
        static char Direct[MAX_DEPTH];
        
        treeType mHead;
        uint64_t * mMark;
        
        // y{x[A][B]}[C] -> x[A]{y[B][C]}
        static treeType zig(treeType p){
            treeType x = p->mLeft;
            p->mLeft = x->mRight;
            x->mRight = p;
            
            return x;
        }

        // y[A]{x[B][C]} -> x{y[A][B]}[C]
        static treeType zag(treeType p){
            treeType x = p->mRight;
            p->mRight = x->mLeft;
            x->mLeft = p;

            return x;
        }

        // 对 g 进行 zig 转换, 对 p 进行 zig 转换
        static treeType zig_zig(treeType g){
            g->mLeft = zig(g->mLeft);
            return zig(g);
        }

        // 对 g 进行 zag 转换, 对 p 进行 zag 转换
        static treeType zag_zag(treeType g){
            g->mRight = zag(g->mRight);
            return zag(g);
        }

        // 对 g 进行 zig 转换, 对 p 进行 zag 转换
        static treeType zig_zag(treeType g){
            g->mLeft = zag(g->mLeft);
            return zig(g);
        }

        // 对 g 进行 zag 转换, 对 p 进行 zig 转换
        static treeType zag_zig(treeType g){
            g->mRight = zig(g->mRight);
            return zag(g);
        }

        // 对树进行伸展
        static void Splay(treeType & head, treeType x, int len){
            for(;len >= 0; len -= 2){
                if(Direct[len] == 'l'){
                    Depth[len]->mLeft = x;
                    // 还有祖父节点
                    if(len > 0){
                        if(Direct[len-1] == 'l'){
                            x = zig_zig(Depth[len-1]);
                        }else if(Direct[len-1] == 'r'){
                            x = zag_zig(Depth[len-1]);
                        }
                    }else // 没有祖父节点
                        x = zig(Depth[len]);
                }else if(Direct[len] == 'r'){
                    Depth[len]->mRight = x;
                    // 还有祖父节点
                    if(len > 0){
                        if(Direct[len-1] == 'l'){
                            x = zig_zag(Depth[len-1]);
                        }else if(Direct[len-1] == 'r'){
                            x = zag_zag(Depth[len-1]);
                        }
                    }else // 没有祖父节点
                        x = zag(Depth[len]);                    
                }
            }

            head = x;
        }

        static void * & BaseVal(){
            static void * val;
            return val; 
        }
        
        static void PrintNode(treeType t, int count = 0, char c = 'h'){
            for(int i = 0; i < count; ++i)
                std::cout<<"  ";
            if(t == nullptr){
                std::cout<<"NULL"<<std::endl;
                return ;
            }
            
            std::cout<<"["<<(void *)t<<": "<<c<<", "<<t->mValue<<", "<<t->mSize<<", "<<t->mCount<<", "<<t->mMark<<"]\n";
            PrintNode(t->mLeft, count+1, 'l');
            PrintNode(t->mRight, count+1, 'r');
        }

        static treeType * FindOnlyByVal(treeType * head, void * val){
            treeType * cur = head;
            while(*cur != nullptr){
                if((*cur)->mValue == val) break;

                if(val > (*cur)->mValue){
                    cur = &((*cur)->mRight);
                }else if(val < (*cur)->mValue){
                    cur = &((*cur)->mLeft);
                }
            }

            return cur;
        }
        
        static treeType FindByAt(treeType head, void * val, int & now){
            treeType cur = head;
            while(cur != nullptr){
                CHECKNOW(now);
                if(cur->isAt(val)) break;
                
                if(val > cur->mValue){
                    Depth[++now] = cur;
                    Direct[now] = 'r';
                    cur = cur->mRight;
                }else if(val < cur->mValue){
                    Depth[++now] = cur;
                    Direct[now] = 'l';
                    cur = cur->mLeft;
                }
            }

            return cur;
        }

        static treeType FindByVal(treeType head, void * val, int & now){
            treeType cur = head;
            while(cur != nullptr){
                CHECKNOW(now);
                if(cur->mValue == val)
                    break;

                if(val > cur->mValue){
                    Depth[++now] = cur;
                    Direct[now] = 'r';
                    cur = cur->mRight;
                }else if(val < cur->mValue){
                    Depth[++now] = cur;
                    Direct[now] = 'l';
                    cur = cur->mLeft;
                }
            }

            return cur;
        }

        static treeType FindMaxVal(treeType head, int & now){
            if(head == nullptr) return head;
            
            treeType cur = head;
            while(cur->mRight != nullptr){
                CHECKNOW(now);
                Depth[++now] = cur;
                Direct[now] = 'r';
                cur = cur->mRight;
            }
            
            return cur;
        }
        
    public:

        memSplayTree():
            mHead(nullptr),
            mMark(new uint64_t[MAX_MARK_SIZE])
            {
                std::memset(mMark, 0, MAX_MARK_SIZE*sizeof(uint64_t));
            }
        
        ~memSplayTree(){
            delete mMark;
            free();
        }

        // 关于 0 mark 为计数内存管理专用，所以当其 mark 为 0 的时候
        // 我们应该默认他为计数器内存的，当该 mark 被删除, 则是程序结束的时候
        // 所以别占用该值，将其留给计数器使用
        inline bool getMark(const unsigned short m){
            uint64_t f = 1;
            return ((f<<m%64)&mMark[m/64]) != 0;
        }

        inline void useMark(const unsigned short m){
            uint64_t f = 1;
            mMark[m/64] |= (f<<m%64);
        }

        inline void unMark(const unsigned short m){
            uint64_t f =1;
            mMark[m/64] &= (~(f<<m%64));
        }
        
        treeType head(){ return mHead; }

        void * insert(int size, unsigned int typesize, int count, unsigned char mark, memAllocFunc fnAlloc, memFreeFunc fnFree){
            treeType node = new nodeType((*fnAlloc)(size), size*typesize, count, mark, fnFree);

            treeType cur = mHead;
            int now = -1;
            while(true){
                if(cur == nullptr){
                    cur = node;
                    break;
                }
                
                CHECKNOW(now);
                if(node->mValue > cur->mValue){
                    Depth[++now] = cur;
                    Direct[now] = 'r';
                    cur = cur->mRight;
                }else if(node->mValue < cur->mValue){
                    Depth[++now] = cur;
                    Direct[now] = 'l';
                    cur = cur->mLeft;
                }else{
                    // std::cout<<"node->mValue = "<<node->mValue<<std::endl;
                    // std::cout<<"cur->mValue = "<<cur->mValue<<std::endl;

                    ALLOCERR();
                    delete node;
                    return nullptr;
                }
            }

            Splay(mHead, node, now);
            // std::cout<<"node->mValue = "<<node->mValue<<std::endl;
            return node->mValue;
        }

        treeType find(void * val){
            int now = -1;
            treeType cur = FindByAt(mHead, val, now);
            if(cur != nullptr)
                Splay(mHead, cur, now);
            
            return cur;
        }

        void erase(void * val){
            // std::cout<<"----- erase "<<val<<" before"<<std::endl;
            // printTree();
            treeType * p = FindOnlyByVal(&mHead, val);
            // std::cout<<"----- p = "<<(void *)p<<std::endl;
            treeType cur = *p;
            if(cur != nullptr){
                treeType ret = cur->mLeft;
                if(ret != nullptr){
                    int now = -1;
                    // 2020-2-4 太有毒了，莫名其妙 double free，弃了弃了
                    // 改用平衡二叉树吧

                    // 2020-2-3 有毒，调用顺序导致大面积出错，警惕啊
                    // archlinux gcc 编译器并没有先执行 FindMaxVal
                    // 有可能是 now -> FindMaxVal() -> ret 导致出错
                    // Splay(ret, FindMaxVal(ret, now), now);
                    treeType max = FindMaxVal(ret, now);
                    Splay(ret, max, now);
                    ret->mRight = cur->mRight;
                    
                    cur->mLeft = nullptr;
                    cur->mRight = nullptr;
                }else
                    ret = cur->mRight;
                
                *p = ret;
            }

            delete cur;
            // printTree();
            // std::cout<<"----- erase after"<<std::endl;
        }

        void free(){
            if(mHead != nullptr){
                delete mHead;
                mHead = nullptr;
            }
        }
        
        // 请输入 lambda 表达式
        template<typename Call>
        void each(const Call & c){
            treeType cur = mHead;
            int now = -1;            
            bool back_flag = false;
            while(cur != nullptr){
                CHECKNOW(now);
                if(!back_flag){
                    Depth[++now] = cur;
                    Direct[now] = 'l';
                    if(cur->mLeft != nullptr){
                        cur = cur->mLeft;
                        continue;
                    }
                }
                
                if(Direct[now] == 'l'){
                    Direct[now] = 'r';
                    if(cur->mRight != nullptr){
                        cur = cur->mRight;
                        back_flag = false;
                        continue;
                    }
                }

                if(Direct[now] == 'r'){
                    if(!c(cur)) return ;
                    cur = now > 0? Depth[--now]:nullptr;
                    back_flag = true;
                }
            }
        }

        // 符合上面规则 mark 0 被计数器给占用
        void freeByMark(const unsigned short mark){
            if(mark == 0) return ;
            
            std::vector<treeType> v;
            each([&v,mark](treeType t)->bool{
                     if(t->mMark == mark)
                         v.push_back(t);
                     return true;
                 });

            for(size_t i = 0; i < v.size(); ++i){
                erase(v[i]->mValue);
            }
        }
        
        void print(){
            std::cout<<"mark: "<<MAX_MARK_SIZE<<std::endl;
            for(int i = 0;i < MAX_MARK_SIZE; ++i)
                std::cout<<std::hex<<mMark[i]<<" ";
            std::cout<<std::dec<<std::endl;
            PrintNode(mHead);
        }

        void printTree(){
            PrintNode(mHead);
        }

        void each_print(){
            each([](treeType t)->bool{
                     std::cout<<"each_print begin -----\n";
                     PrintNode(t); 
                     std::cout<<"each_print end -----\n";
                     return true;
                 });
        }
    };

    typename memSplayTree::treeType memSplayTree::Depth[memSplayTree::MAX_DEPTH] = {0};
    char memSplayTree::Direct[memSplayTree::MAX_DEPTH] = {0};
}

#endif
